ABC283 D - Scope

提出

WA

code: python

s = list(input())

q = set()

# a((()))a

print("No")

exit()

# a((()))ab

l = set()

r = set()

for i in s:

if i == "(" or i == ")":

break

else:

l.add(i)

for i in reversed(s):

if i == "(" or i == ")":

break

else:

r.add(i)

for i in l:

if i in r:

print("No")

exit()

for i in s:

if i == "(":

continue

elif i == ")":

q.clear()

else:

if i in q:

print("No")

exit()

else:

q.add(i)

print("Yes")

解答

code: python

from collections import defaultdict

S = input()

# 中断した () を管理するリスト

x = []

# a ～ z がすでに箱に入っているか管理

y = defaultdict(int)

# 今見ている () の中身を管理

now = set()

for s in S:

# 新しい () の登場にあわせて、今見ている () を X に格納

if s == "(":

x.append(now)

now = set()

continue

if s == ")":

# 今見ている () の中身をキーに X を初期化

for t in now:

# 直前の () を取り出す

now = x.pop()

continue

# 被りを検出したら終了

print("No")

exit()

# s を使用済みに変更

# 今見ている () に s が存在することを記録

now.add(s)

print("Yes")

メモ

提出

code: python

from collections import deque

s = list(input())

c = set()

q = deque()

for v in s:

if v == "(":

q.append(v)

elif v == ")":

while q:

qv = q.pop()

if qv in c:

c.remove(qv)

if qv == "(":

break

else:

q.append(v)

if v in c:

print("No")

exit()

else:

c.add(v)

print("Yes")